<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    function getSeq(arr) {
        debugger
        let result = [0]
        const len = arr.length // 总长度
        let resultLastIndex
        let start
        let end
        let middle = 0
        let p = arr.slice(0).fill(0)
        for (let i = 0; i < len; i++) {
            const arrI = arr[i]
            if (arrI != 0) {
                // 获取队列中的最后一项
                resultLastIndex = result[result.length - 1]
                if (arr[resultLastIndex] < arrI) {
                    result.push(i)
                    p[i] = resultLastIndex
                    continue
                }
                // ..替换
                start = 0
                end = result.length - 1
                while (start < end) { // 折半 查找
                    middle = Math.floor((start + end) / 2)
                    // 中间那一项的值
                    // 1,2,3,4,6    5
                    if (arr[result[middle]] < arrI) {
                        start = middle + 1
                    } else {
                        end = middle
                    }
                }
                if (arrI < arr[result[end]]) {
                    p[i] = result[end - 1]
                    result[end] = i // 发现最后找到的索引比这一项大，那就用这个索引换掉，因为更有潜力
                }
            }
        }
        let i = result.length
        let last = result[i - 1]
        debugger
        while (i-- > 0) {
            result[i] = last
            last = p[last]
        }
        return result
    }

    console.log(getSeq([2, 3, 1, 5, 9, 4]))
</script>

</body>
</html>
